#include <atomic>
#include <memory>
#include <iostream>
#include <thread>
#include <vector>
#include <chrono>

// 定义模板类型的无锁栈
template<typename T>
class LockFreeStack {
private:
    // 内部节点结构
    struct Node {
        std::shared_ptr<T> data;  			// 节点存储的数据，使用智能指针自动管理内存
        Node* next;               			// 指向下一个节点的指针

        // 节点构造函数
        Node(const T& data_) : data(std::make_shared<T>(data_)), next(nullptr) {}
    };

    // 原子类型的头节点指针
    std::atomic<Node*> head;

public:
    // 向栈中压入元素
    void push(const T& data) {
        Node* new_node = new Node(data);	// 创建新节点
        new_node->next = head.load(std::memory_order_relaxed);  // 仅需读取head的当前值，不关心与其他内存操作的顺序

        // 尝试将新节点设置为头节点，直到成功为止
        while (!head.compare_exchange_weak(new_node->next, new_node,
                                           std::memory_order_release,
                                           std::memory_order_relaxed));
    }

    // 从栈中弹出元素
    std::shared_ptr<T> pop() {
        Node* old_head = head.load(std::memory_order_relaxed);	// 读取头节点
        // 尝试更新头节点为其下一个节点，直到成功或栈为空
        while (old_head != nullptr && !head.compare_exchange_weak(old_head,
                                                                  old_head->next,
                                                                  std::memory_order_release,
                                                                  std::memory_order_relaxed));
        // 如果头节点存在，则返回数据，否则返回空指针
        return old_head ? old_head->data : std::shared_ptr<T>();
    }
};

int main() {
    LockFreeStack<int> stack;
    const int NUM_OPERATIONS = 1000000;  						// 定义操作次数

    auto start_time = std::chrono::high_resolution_clock::now();	// 记录开始时间

    // 启动一个生产者线程进行数据入栈
    std::thread producer([&]() {
        for (int i = 0; i < NUM_OPERATIONS; ++i) {
            stack.push(i);
        }
    });

    producer.join();  										// 等待生产者线程结束

    // 启动一个消费者线程进行数据出栈
    std::thread consumer([&]() {
        for (int i = 0; i < NUM_OPERATIONS; ++i) {
            auto item = stack.pop();
            if (!item) {  										// 检查是否成功出栈
                std::cout << "Pop failed: stack might be empty" << std::endl;
            }
        }
    });

    consumer.join();  										// 等待消费者线程结束

    auto end_time = std::chrono::high_resolution_clock::now();  	// 记录结束时间
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count();  											// 计算总耗时

    // 输出操作的总时间
    std::cout << "Total time for " << 2 * NUM_OPERATIONS << " operations: " << duration << " ms" << std::endl;
    return 0;
}